// ml:run = time -p $bin < 1008.in
#include <cstdio>
#include <cmath>
#include <algorithm>

template <class T>
void scan(T & a)
{
	a = 0;
	bool flag = false;
	char ch = std::getchar();
	if (ch == '-')
		flag = true;
	else if (ch >= '0' && ch <= '9')
		a = ch - '0';

	while ((ch = std::getchar()) >= '0' && ch <= '9')
		a = a * 10 + ch - '0';
	if (flag) a = -a;
}

using ll = long long;
int const maxn = 100007;
int n, m;
ll a[maxn];

struct node
{
    ll sum, min, max, d, same; // same: 0 for different
};

node tree[4 * maxn];

void push_down(int id, int l, int r);

void push_up(int id, int l, int r)
{
    auto & t = tree[id];
    int mid = (l + r) / 2;
    push_down(id * 2, l, mid);
    push_down(id * 2 + 1, mid + 1, r);
    t.max = std::max(tree[id * 2].max, tree[id * 2 + 1].max);
    t.min = std::min(tree[id * 2].min, tree[id * 2 + 1].min);
    t.same = tree[id * 2].same == tree[id * 2 + 1].same ? tree[id * 2].same : 0;
    t.sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
    t.d = 0;
}

void push_down(int id, int l, int r)
{
    auto & t = tree[id];
    if (t.d) {
        if (l != r) { tree[id * 2].d += t.d; tree[id * 2 + 1].d += t.d; }
        t.sum += t.d * (r - l + 1);
        t.min += t.d; t.max += t.d;
        if (t.same) t.same += t.d;
        t.d = 0;
    }
}

void build(int id, int l, int r)
{
    if (l == r) {
        auto & t = tree[id];
        t.sum = t.min = t.max = t.same = a[l];
        t.d = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    push_up(id, l, r);
    if (tree[id].d) exit(1);
}

void tree_add(int id, int l, int r, int tl, int tr, ll x)
{
    push_down(id, l, r);
    if (tl <= l && r <= tr) {
        tree[id].d += x;
        push_down(id, l, r);
        return;
    }
    int mid = (l + r) / 2;
    if (tl <= mid) tree_add(id * 2, l, mid, tl, tr, x);
    if (tr > mid) tree_add(id * 2 + 1, mid + 1, r, tl, tr, x);
    push_up(id, l, r);
}

void tree_sqrt(int id, int l, int r, int tl, int tr)
{
    push_down(id, l, r);
    if (l == r) {
        auto & t = tree[id];
        t.sum = sqrt(t.sum);
        t.same = t.sum;
        t.max = t.min = t.sum;
        return;
    }
    if (tl <= l && r <= tr) {
        auto & t = tree[id];
        if (t.same) {
            t.d -= t.same - (ll)sqrt(t.same);
            push_down(id, l, r);
            return;
        } else {
            if (t.max - t.min <= 1) {
                ll tmax = sqrt(t.max);
                ll tmin = sqrt(t.min);
                if (tmax - tmin == 1) {
                    t.d -= (t.max - tmax);
                    push_down(id, l, r);
                    return;
                }
            }
        }
    }
    int mid = (l + r) / 2;
    if (tl <= mid) tree_sqrt(id * 2, l, mid, tl, tr);
    if (tr > mid) tree_sqrt(id * 2 + 1, mid + 1, r, tl, tr);
    push_up(id, l, r);
}

ll tree_query(int id, int l, int r, int tl, int tr)
{
    push_down(id, l, r);
    if (tl <= l && r <= tr) {
        auto & t = tree[id];
        return t.sum;
    }
    int mid = (l + r) / 2;
    ll ret = 0;
    if (tl <= mid) ret += tree_query(id * 2, l, mid, tl, tr);
    if (tr > mid) ret += tree_query(id * 2 + 1, mid + 1, r, tl, tr);
    push_up(id, l, r);
    return ret;
}

int main()
{
    int T; scan(T);
    while (T--) {
        scan(n); scan(m);
        for (int i = 1; i <= n; i++) scan(a[i]);
        build(1, 1, n);
        for (int i = 0, op, l, r, x; i < m; i++) {
            scan(op); scan(l); scan(r);
            if (op == 1) {
                scan(x);
                tree_add(1, 1, n, l, r, x);
            } else if (op == 2) {
                tree_sqrt(1, 1, n, l, r);
            } else if (op == 3) {
                printf("%lld\n", tree_query(1, 1, n, l, r));
            }
        }
    }
}

